package LeetCode.month02.day44;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int left = newInterval[0];
        int right = newInterval[1];
        int i = 0;
        int n = intervals.length;
        while(i<n&&intervals[i][1]<left){
            res.add(intervals[i++]);
        }
        while(i<n&&intervals[i][0]<=right){
            left = Math.min(left,intervals[i][0]);
            right = Math.max(right,intervals[i][1]);
            i++;
        }
        res.add(new int[]{left,right});
        while(i<n){
            res.add(intervals[i++]);
        }
        return res.toArray(new int[res.size()][]);
    }
}
